package bstsetcode.stanforduniversity18;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/15 17:19
 * 问题4的链表实现
 *
 */
public class LinkedList<E> {

    private class Node{
        E e;
        Node next;


        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e){
            this(e,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }


    private Node dummyHead;
    private int size;

    public LinkedList() {
        this.dummyHead=new Node(null,null);
        this.size = 0;
    }


    //4个方法

    public void addFirst(E e){
        add(0,e);
    }
    //注意这个addlast()  的索引位置
    public void addLast(E e){
        add(size,e);
    }

    private void add(int index, E e) {
        if(index < 0 || index > size){
            throw new IllegalArgumentException("非法的参数索引");
        }

        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        prev.next = new Node(e,prev.next);
        size++;
    }

    public E removeFirst(){
        return remove(0);
    }

    public E removeLast(){
        return remove(size-1);
    }

    private E remove(int index) {

        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node oldNode = prev.next;
        prev.next = oldNode.next;
        oldNode.next=null;
        size--;

        return oldNode.e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("LinkedList front:");
        Node cur = dummyHead.next;
        while (cur!=null){
            res.append(cur).append("->");
            cur =  cur.next;
        }
        res.append("NUll  tail");
        return res.toString();
    }

    private void insertNth(int index, E e) {
        if(index < 0 || index > size){
            throw new IllegalArgumentException("非法的参数索引");
        }

        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        prev.next = new Node(e,prev.next);
        size++;
    }

}
